package leetcode.median;

/**
 * ClassName: $474_FindMaxForm
 * Description:
 * date: 2022-01-25 12:11
 *
 * @author liyifan
 */
public class $474_FindMaxForm {
    public int findMaxForm(String[] strs, int m, int n) {
        int NUM = strs.length;
        int[][] arr = new int[NUM][2];
        for (int i = 0;i < NUM;i++) {
            for (Character c:strs[i].toCharArray()) {
                if (c == '0')
                    arr[i][0]++;
                else
                    arr[i][1]++;
            }
        }
        // 转化为二维背包 限制条件为m n
        int[][] dp = new int[m + 1][n + 1];//    dp[i][j][k]表示0-i的字符串中，满足sum(0) <= j,sum(1)<=k的子集个数
        for (int i = 1;i <= NUM;i++) {
            int zeros = arr[i - 1][0];
            int ones = arr[i - 1][1];
            for (int j = m;j >= zeros;j--) {
                for (int k = n;k >=ones;k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
